class Solution {
    /*
    可以发现的是，我们将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。
    拿示例来看，我们从 6 这个位置分开以后数组变成了 [4, 5, 6] 和 [7, 0, 1, 2] 两个部分，
    其中左边 [4, 5, 6] 这个部分的数组是有序的，其他也是如此。

    这启示我们可以在常规二分查找的时候查看当前 mid 为分割位置分割出来的两个部分 [l, mid] 
    和 [mid + 1, r] 哪个部分是有序的，
    并根据有序的那个部分确定我们该如何改变二分查找的上下界，
    因为我们能够根据有序的那部分判断出 target 在不在这个部分：

作
    */
    public int search(int[] nums, int target) {
        int l=0, r=nums.length-1;
        while( l<=r ){
            int mid = (l+r)/2;
            if( nums[mid]==target )
                return mid;
            /*
                分成两部分[l,mid]和[mid+1,r]
            */
            if( nums[l]<=nums[mid] ){  // 如果左边有序
                if( target>=nums[l] && target<=nums[mid] )
                    r = mid-1;
                else
                    l = mid+1;
            }
            else{
                if( target>=nums[mid] && target<=nums[r] )
                    l = mid+1;
                else
                    r = mid-1;
            }
        }
        return -1;
    }
}